# 介绍
图中的元素称为顶点（vertex），顶点间的联系称为边（edge）。边有方向则称为有向图，无方向称为无向图，边具有权重的称为带权图（weighted graph）。无向图中，顶点的度（degree）等于与顶点相连的边数，有向图中则分为入度（in-degree）和出度（out-degree）
# 图的存储方法
# 邻接矩阵（Adjacency Matrix）
- 优点：简单直接，能够高效获取顶点间关系，方便图的计算
- 缺点：容易浪费空间，比如对于无向图，矩阵沿对角线对称，实际只需存储一半；对于稀疏图，更是造成大量空间浪费
# 邻接表（Adjacency List）
- 优点：节省存储空间，更适合存储稀疏图
- 缺点：使用时，较为耗时间，且对缓存不友好
对于有向图，对应顶点的链表通常存储了其指向的顶点，这不利于查找指向该顶点的顶点集合，解决方法是再增加一个逆邻接表
由于使用了链表，因此与散列表的优化方法相同，当链表过长时，可以转化为更高效的数据结构，如跳表、平衡二叉树等，加快查找效率
public class Graph { // 无向图
private int v; // 顶点的个数
private LinkedList<Integer> adj[]; // 邻接表
public Graph(int v) {
this.v = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i) {
adj[i] = new LinkedList<>();
}
}
public void addEdge(int s, int t) { // 无向图一条边存两次
adj[s].add(t);
adj[t].add(s);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 图的搜索
# 广度优先搜索（Breadth-First-Search）
主要思想：先查找离起始顶点最近的，接着查找次近的，逐层向外搜索
BFS 的通常需要借助 queue 和 visited 数组来实现逐层搜索，借助 prev 数组来存储搜索的路径
复杂度：
- 时间：
O(E)，每个顶点进出一次队列，每条边被访问一次，E 通常大于等于 V-1，可以简写为O(E) - 空间：
O(V)，几个辅助结构的大小都不会超过顶点的个数
# 深度优先搜索（Depth-First-Search）
主要思想：本质是回溯的思想，选择一条搜索路径直到终点，如果未找到，则返回上一个分支点继续搜索
DFS 同样需要 visited 和 prev 数组的帮助，通常 DFS 天然适合使用递归来实现，但是当数据量较大，存在递归栈溢出风险时，可以使用 stack 完成迭代实现
复杂度：
- 时间：
O(E)，每条边最多被访问两次，一次遍历，一次退回 - 空间：
O(V)，递归调用栈和辅助结构大小都不会超过顶点个数